package com.algorithm.cjm.csnote

/**
 * 二叉堆
 * 1. 如何定位到最后一个 父节点？
 * 2. 如果整个数组的长度是 奇数，那么最后一个元素是右节点
 * 根据公式  2 * parent + 2 = arr.length - 1  ;  parent = (arr.length - 1 - 2) / 2  等同于 (arr.length - 2) / 2
 *
 * 3. 如果整个数组长度是 偶数，那么最后一个元素是左节点
 *
 * 根据公式  2 * parent + 1 = arr.length - 1  ;  parent = (arr.length - 2) / 2  等同于 (arr.length - 2) / 2
 *
 * Created by jieming.chen on 2021/2/11
 */
fun main(args: Array<String>) {
    buildHeap(intArrayOf(7, 1, 3, 10, 5, 2, 8, 9, 6))

    upAdjust(intArrayOf(7, 1, 3, 10, 5, 2, 8, 9, 6))
}

/**
  *  // 数组的长度 为 9
  *  // 2 * n + 2 = 9 - 1
  *  // n = 3
  *
  *  // 数组的长度 为 10
  *  // 2 * n + 1 = 10 - 1i
  *  // n = 4
 */
fun buildHeap(array: IntArray): Unit {
    val parent = (array.size - 2)/2
    for (i in parent downTo 0) downAdjust(array, i, array.size)
    println(array.contentToString())
}

/**
 * 下沉调整
 * 1. 父节点值存储 在临时变量
 * 2. 父节点的值和两个子节点的值 进行比较
 * 3. 子节点替换到 父节点的位置
 * 4. 父节点 继续下沉比较，直到不可以比较为止
 * 5. 父节点 值 替换
 *
 */
fun downAdjust(array: IntArray, parentIndex1: Int, length: Int) {
    var parentIndex = parentIndex1

    val temp = array[parentIndex]
    var childIndex = 2 * parentIndex + 1

    while (childIndex < length) {
        // 两两比较，左孩子和右孩子进行比较
        if (childIndex + 1 < length && array[childIndex + 1] < array[childIndex]) {
            childIndex ++
        }
        if (temp <= array[childIndex]) {
            break
        }
        array[parentIndex] = array[childIndex]
        parentIndex = childIndex

        childIndex = 2 * childIndex + 1
    }
    array[parentIndex]  = temp
}

/**
 * “上浮” 调整
 * 新增一个元素的场景下
 * 1. 最后一个元素，上浮，根据最后一个元素，反向推导父元素的坐标
 * 2. 把最后一个元素的值，暂时存储在 临时变量里面
 * 3. 比较最后一个元素的值 和 父节点的值， 如果小于父节点，则父节点的值 赋值给 叶子节点(也就是最后一个元素的值)
 * 4. childIndex， parentIndex 依次向上替换。 依次比较
 * 5. 把 temp 的值 复制给最后一个不可以再换取位置的点
 */
fun upAdjust(array: IntArray) {
    var childIndex = array.size - 1
    var parentIndex = (childIndex - 1) / 2

    val temp = array[childIndex]
    while (childIndex > 0 && temp < array[parentIndex]) {
        // 无须真正交换，单向赋值即可
        array[childIndex] = array[parentIndex]
        childIndex = parentIndex
        parentIndex = (parentIndex - 1) / 2
    }
    array[childIndex] = temp

    println(array.contentToString())
}